Search for: All records

The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. Specifically, we observe an undirected and unweighted graph on n vertices. Under the null hypothesis, the graph is a realization of an Erdös-R{\'e}nyi graph with edge probability (or, density) q. Under the alternative, there is a subgraph on k vertices with edge probability p>q. The statistical as well as the computational barriers of this problem are well-understood for a wide range of the edge parameters p and q. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph. We also propose a polynomial-time algorithm which is able to detect the planted subgraph, albeit with more queries compared to the above lower bound. We conjecture that in the leftover regime, no polynomial-time algorithms exist. Our results resolve two open questions posed in the past literature. 

ABSTRACTDrilling vibrations can cause inefficient drilling and accelerated damage to system components. Therefore, reducing or eliminating such vibrations is a major focus area for natural gas and geothermal drilling applications. One particularly important vibration mode is stick-slip. Stick-slip occurs when the bottom-hole angular velocity starts oscillating while the top hole angular velocity remains relatively constant. This not only causes poor drilling, it is also difficult to detect using surface sensors. In this work, we describe the development and testing of a benchtop drilling system for studying stick-slip dynamics and mitigation. We show how this system can produce stick-slip oscillations. Next, we use this data to formulate a data-driven rock-bit interaction model. This model can be combined with linear systems analysis to predict stick-slip and understand mitigation methods. We describe out instrumentation that enables closed-loop control under simulated communications constraints. We conclude by providing preliminary experimental data on bench-level stick-slip. INTRODUCTIONExploration via autonomous drilling processes for geothermal resources is an important focus area for drilling research. However, to fully realize the clean-energy promise of geothermal energy, key challenges still need to be resolved.Issues arising in the drilling process often originate from a drillstring's increased susceptibility to vibrational oscillations as depths increase. Some examples of drilling vibrations include stick-slip (Navarro-Lopez and Suarez, 2004), bit-bounce (Spanos et al., 1995), and whirl (Jansen, 1991). Torsional oscillations are the focus of this work.Torsional vibrations result in a destructive phenomenon known as stick-slip. Initiated at the bit-rock surface, the drillstring bit experiences large angular velocity oscillations not seen at the surface (Pavone and Desplans, 1994; Besselink et al., 2011; Kessai et al., 2020). Stick-slip results in premature bit wear and drillstring fracture.Stick-slip is a fundamentally nonlinear and unpredictable phenomena. Stick-slip results from the combination of bit-rock interactions and drillstring compliance. As a result, there is a key need for experimental studies of stick-slip dynamics and mitigation. 

Context. With the advent of space-based asteroseismology, determining accurate properties of red-giant stars using their observed oscillations has become the focus of many investigations due to their implications in a variety of fields in astrophysics. Stellar models are fundamental in predicting quantities such as stellar age, and their reliability critically depends on the numerical implementation of the physics at play in this evolutionary phase. Aims. We introduce the Aarhus red giants challenge, a series of detailed comparisons between widely used stellar evolution and oscillation codes that aim to establish the minimum level of uncertainties in properties of red giants arising solely from numerical implementations. We present the first set of results focusing on stellar evolution tracks and structures in the red-giant-branch (RGB) phase. Methods. Using nine state-of-the-art stellar evolution codes, we defined a set of input physics and physical constants for our calculations and calibrated the convective efficiency to a specific point on the main sequence. We produced evolutionary tracks and stellar structure models at a fixed radius along the red-giant branch for masses of 1.0  M ⊙ , 1.5  M ⊙ , 2.0  M ⊙ , and 2.5  M ⊙ , and compared the predicted stellar properties. Results. Once models have been calibrated on the main sequence, we find a residual spread in the predicted effective temperatures across all codes of ∼20 K at solar radius and ∼30–40 K in the RGB regardless of the considered stellar mass. The predicted ages show variations of 2–5% (increasing with stellar mass), which we attribute to differences in the numerical implementation of energy generation. The luminosity of the RGB-bump shows a spread of about 10% for the considered codes, which translates into magnitude differences of ∼0.1 mag in the optical V -band. We also compare the predicted [C/N] abundance ratio and find a spread of 0.1 dex or more for all considered masses. Conclusions. Our comparisons show that differences at the level of a few percent still remain in evolutionary calculations of red giants branch stars despite the use of the same input physics. These are mostly due to differences in the energy generation routines and interpolation across opacities, and they call for further investigation on these matters in the context of using properties of red giants as benchmarks for astrophysical studies. 

Contact. The large quantity of high-quality asteroseismic data that have been obtained from space-based photometric missions and the accuracy of the resulting frequencies motivate a careful consideration of the accuracy of computed oscillation frequencies of stellar models, when applied as diagnostics of the model properties. Aims. Based on models of red-giant stars that have been independently calculated using different stellar evolution codes, we investigate the extent to which the differences in the model calculation affect the model oscillation frequencies and other asteroseismic diagnostics. Methods. For each of the models, which cover four different masses and different evolution stages on the red-giant branch, we computed full sets of low-degree oscillation frequencies using a single pulsation code and, from these frequencies, typical asteroseismic diagnostics. In addition, we carried out preliminary analyses to relate differences in the oscillation properties to the corresponding model differences. Results. In general, the differences in asteroseismic properties between the different models greatly exceed the observational precision of these properties. This is particularly true for the nonradial modes whose mixed acoustic and gravity-wave character makes them sensitive to the structure of the deep stellar interior and, hence, to details of their evolution. In some cases, identifying these differences led to improvements in the final models presented here and in Paper I; here we illustrate particular examples of this. Conclusions. Further improvements in stellar modelling are required in order fully to utilise the observational accuracy to probe intrinsic limitations in the modelling and improve our understanding of stellar internal physics. However, our analysis of the frequency differences and their relation to stellar internal properties provides a striking illustration of the potential, in particular, of the mixed modes of red-giant stars for the diagnostics of stellar interiors.